In [1]:
#!/usr/bin/python
#-*- coding: utf-8 -*-

决策树

本章采用ID3算法构造决策树
ID3算法仅适用于标称型数据

基本思路：根据已有特征和标签寻找最佳的分类方案（香农熵最佳）
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据
缺点：可能会产生过度匹配问题
适用数据类型：数值型（离散化）的标称型

香农熵

如果待分类的事务可能划分在多个分类中，则符号\(x_i\)（\(p(x_i)\)为选择该分类的概率）的信息定义为：\(l(xi)=-log{2}p(xi)\)
则香农熵即为所有可能值的信息期望值：\(H=-\sum{i=1}^{n}p(xi)log{2}p(x_i)\)

In [2]:
import trees

选择最佳的数据集划分

  1. 逐一选取其中一个特征为分类依据
  2. 根据上述分类依据计算各个子集的香农熵
  3. 计算划分后子集的加权平均数（以子集大小为权）作为划分数据集后总体的香农熵
  4. 找到使总体香农熵最大的划分方案
In [3]:
# 获取数据集
# 数据集格式：列表，每一行包括一系列特征值和标签（标签为最后一个元素）
dataSet, labels = trees.createDataSet()
print(dataSet)

[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
In [7]:
# 特征值的数量（假定每一行数据格式一致）
numFeatures = len(dataSet[0]) - 1
# 原始香农熵
baseEntropy = trees.calcShannonEnt(dataSet)
# 最佳信息增益
bestInfoGain = 0.0
# 最佳信息增益对应的特征索引
bestFeature = -1
In [8]:
# 逐一尝试，找到最佳的划分方案
for i in range(numFeatures):
    # 获取特征值的集合
    featList = [example[i] for example in dataSet]
    uniqueVals = set(featList)    # 通过取集合的方式去除重复元素
    # 计算总体的香农熵
    newEntropy = 0.0
    for value in uniqueVals:
        # 按给定特征划分数据集 
        # 原始数据集dataSet，选取索引为i的特征，筛选其值为value的所有项
        subDataSet = trees.splitDataSet(dataSet, i , value)
        # 权值
        prob = len(subDataSet) / float(len(dataSet))
        # 累加
        newEntropy += prob * trees.calcShannonEnt(subDataSet)
    # 计算香农熵增益
    infoGain = baseEntropy - newEntropy
    # 如果出现更佳的划分方案（香农熵增益更高）
    if infoGain > bestInfoGain:
        bestInfoGain = infoGain
        bestFeature = i
In [10]:
# 结果
print(bestInfoGain)
print(bestFeature)
print(dataSet)

0.419973094022
0
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

递归构建决策树

多次寻找最佳划分方案，直到某一分支都属于同一分类或所有特征值都使用完，从而构建出决策树
如果所有特征值都使用完还未能决定出该分支的分类，则采用举手表决的方式决定

In [11]:
myDat, labels = trees.createDataSet()
In [12]:
myTree = trees.createTree(myDat, labels)
In [13]:
print(myTree)

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
In [ ]: